import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        // 创建dp表、初始化、填表、返回值
        int n = arr.length;
        int[][] dp = new int[n][n];

        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < n; i++) {
            // 绑定 元素值 和 下标的关系
            hash.put(arr[i], i);
        }

        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 2); // 只能填充一维数组
        }

        int ret = 2;
        // 斐波那契子序列最少要有三个才行
        // 因此 i = 2, j = 1, k = 0这是最基本的
        for (int i = 2; i < n; i++) {
            for (int j = 1; j < i; j++) { // j 要小于 i
                // 填的是一个dp[i][j]
                int a = arr[i] - arr[j];
                // 存在a，且 a < arr[j]
                if (hash.containsKey(a) && a < arr[j]) {
                    // 注意这里的写法 dp[j][i]
                    dp[j][i] = dp[hash.get(a)][j] + 1; // 子序列长度+1
                    ret = Math.max(dp[j][i], ret);
                }
            }
        }

        // 由于数组全部初始化为2了，因此可能原来是0的情况，也变为了2
        return ret == 2 ? 0 : ret;
    }
}